package agorithm.week1.classTwo;

/**
 * 1248. 统计「优美子数组」
 * 给你一个整数数组 nums 和一个整数 k。
 *
 * 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
 *
 * 请返回这个数组中「优美子数组」的数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,2,1,1], k = 3
 * 输出：2
 * 解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
 * 示例 2：
 *
 * 输入：nums = [2,4,6], k = 1
 * 输出：0
 * 解释：数列中不包含任何奇数，所以不存在优美子数组。
 * 示例 3：
 *
 * 输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
 * 输出：16
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 50000
 * 1 <= nums[i] <= 10^5
 * 1 <= k <= nums.length
 */
public class NumberOfSubarrays {

    public static void main(String[] args) {
        int[] digits = {2,2,2,1,2,2,1,2,2,2};
        int arr = numberOfSubarrays(digits,2);
        System.out.println("max = " + arr);
    }

    public static int numberOfSubarrays(int[] nums, int k) {
        // 求奇数数字的前缀和 得到sum = [ 0 , 1, 2, 2, 3, 4]
        int[] sum = new int[nums.length+1];
        for ( int i = 1 ;i <= nums.length ;i++){
            sum[i] = sum[i-1] + nums[i-1] % 2;
        }

        int ans = 0;
        // 第一暴力 ：求 s[i] - s[j] = k;
        // for ( int i = 0 ;i < sum.length ;i++){
        //     for ( int j = 0 ;j < i ; j++){
        //         if(sum[i] - sum[j] == k){
        //             ans++;
        //         }
        //     }
        // }
        // 优化
        // count 计数 记录 所有sum的次数
        // sum = [ 0 , 1, 2, 2, 3, 4]
        // 得到 0 一次，1 一次，2 两次 ，3 一次 ，4一次
        // sum[i] - sum[j] == k ===> sum[j] = sum[i] - k;
        int[] count = new int[sum.length];
        for ( int i = 0 ;i < sum.length ;i++){
            count[sum[i]] += 1;
        }
        for ( int i = 0 ;i < count.length ;i++){
            if(sum[i]>=k){
                ans += count[sum[i]-k];
            }
        }

        return ans;
    }
}
